﻿namespace QQ.InterviewQuestions.LinkedList
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    class NodeList
    {
        private Node head = null;
        
        public int Count
        {
            get
            {
                int count = 0;
                Node node = head;
                while (node != null)
                {
                    count++;
                    node = node.Next;
                }

                return count;
            }

            private set
            {
            }
        }

        public void Append(Node newNode)
        {
            if (head == null)
            {
                head = newNode;
            }
            else
            {
                // Add to end of list
                Node node = head;
                while (node.Next != null)
                {
                    node = node.Next;
                }

                node.Next = newNode;
            }
        }

        public void Display()
        {
            Node node = head;

            while (node != null)
            {
                Console.WriteLine(node.Value);
                node = node.Next;
            }
        }

        public void DisplayRandom()
        {
            Node node = head;

            while (node != null)
            {
                Console.WriteLine(node.Random.Value);
                node = node.Next;
            }
        }

        public void Random()
        {
            head.Random = head.Next.Next;
            head.Next.Random = head;
            head.Next.Next.Random = head.Next.Next.Next;
            head.Next.Next.Next.Random = head.Next;
        }

        public NodeList Clone()
        {
            Node p;
            Node q;
            int origCount;
            origCount = Count;

            // step one: insert new nodes between nodes of the list 
            for (p = head; p != null; p = p.Next.Next)
            {
                q = p.Next;
                p.Next = new Node(p.Value);
                p.Next.Next = q;
            }

            // step two: copy the other pointers 
            for (p = head; p != null; p = p.Next.Next)
            {
                p.Next.Random = p.Random.Next;
            }

            // step three: separate the lists 
            q = head.Next;
            Node r = q;
            int count = 0;
            for (p = head; p != null; p = p.Next)
            {
                count++;
                if (count == origCount)
                {
                    p.Next = null;
                }
                else
                {
                    p.Next = p.Next.Next;
                }

                if (q.Next != null)
                {
                    q.Next = q.Next.Next;
                }
                
                q = q.Next;
            }

            NodeList list = new NodeList();
            list.Append(r);

            return list;
        }
    }
}
